package cn.z2huo.algorithm.greedy.activityPlan;

import java.util.ArrayList;
import java.util.List;

public class ActivityPlan {

    public void resolve(int[] start, int[] end){
        List list = new ArrayList();

        // 对活动数组按照结束时间进行排序
        sort(start, end);
        System.out.println("按照结束时间排好序的活动数组为：");
        printArray(start);
        printArray(end);

        // 先将最早结束的活动添加到活动列表中
        list.add(0);
        int flag = 0;   // 用来表示活动队列中最后的一个活动的数组标示
        // 找出下一个满足条件的活动并添加到列表中
        for(int i=1; i<start.length; i++){
            if(start[i] > end[flag]){
                list.add(i);
                flag = i;
            }
        }
        System.out.println("最后的活动安排为：");
        for(int i=0; i<list.size(); i++){
            System.out.printf("%2d --- %2d \n", start[(int) list.get(i)], end[(int) list.get(i)]);
        }
        System.out.println("所能安排的活动数量为："+list.size());
    }

    // 输出一维数组
    public void printArray(int[] array){
        for (int i = 0; i < array.length; i++) {
            System.out.printf("%3d", array[i]);
        }
        System.out.println();
    }
    // 简单选择排序
    public void sort(int[] start, int[] end){
        for(int i=0; i<end.length; i++){
            for(int j=i+1; j<end.length; j++){
                if(end[j] < end[i]){
                    int flag = start[j];
                    start[j] = start[i];
                    start[i] = flag;

                    flag = end[j];
                    end[j] = end[i];
                    end[i] = flag;
                }
            }
        }
    }

    public static void main(String[] args){
        int[] start = {6, 3, 0, 3, 5, 1, 5, 8, 2, 12, 8};
        int[] end = {10, 8, 6, 5, 7, 4, 9, 11, 13, 14, 12};

        ActivityPlan ap = new ActivityPlan();
        System.out.println("没有排序的活动数组为：");
        ap.printArray(start);
        ap.printArray(end);
        ap.resolve(start, end);
    }
}
